home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / FLEX-TC_ / PARSE.Y < prev    next >
Text File  |  1990-01-02  |  13KB  |  653 lines
  1. /* parse.y - parser for flex input */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. %token CHAR NUMBER SECTEND SCDECL XSCDECL WHITESPACE NAME PREVCCL EOF_OP
  28.  
  29. %{
  30.  
  31. #include "flexdef.h"
  32.  
  33. #ifndef lint
  34.  
  35. static char copyright[] =
  36.     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  37. static char CR_continuation[] = "@(#) All rights reserved.\n";
  38.  
  39. static char rcsid[] =
  40.     "@(#) $Header: parse.y,v 2.1 89/06/20 17:23:54 vern Exp $ (LBL)";
  41.  
  42. #endif
  43.  
  44. int pat, scnum, eps, headcnt, trailcnt, anyccl, lastchar, i, actvp, rulelen;
  45. int trlcontxt, xcluflg, cclsorted, varlength, variable_trail_rule;
  46. char clower();
  47.  
  48. static int madeany = false;  /* whether we've made the '.' character class */
  49. int previous_continued_action;    /* whether the previous rule's action was '|' */
  50.  
  51. %}
  52.  
  53. %%
  54. goal            :  initlex sect1 sect1end sect2 initforrule
  55.             { /* add default rule */
  56.             int def_rule;
  57.  
  58.             pat = cclinit();
  59.             cclnegate( pat );
  60.  
  61.             def_rule = mkstate( -pat );
  62.  
  63.             finish_rule( def_rule, false, 0, 0 );
  64.  
  65.             for ( i = 1; i <= lastsc; ++i )
  66.                 scset[i] = mkbranch( scset[i], def_rule );
  67.  
  68.             if ( spprdflt )
  69.                 fputs( "YY_FATAL_ERROR( \"flex scanner jammed\" )",
  70.                    temp_action_file );
  71.             else
  72.                 fputs( "ECHO", temp_action_file );
  73.  
  74.             fputs( ";\n\tYY_BREAK\n", temp_action_file );
  75.             }
  76.         ;
  77.  
  78. initlex         :
  79.             {
  80.             /* initialize for processing rules */
  81.  
  82.             /* create default DFA start condition */
  83.             scinstal( "INITIAL", false );
  84.             }
  85.         ;
  86.             
  87. sect1        :  sect1 startconddecl WHITESPACE namelist1 '\n'
  88.         |
  89.         |  error '\n'
  90.             { synerr( "unknown error processing section 1" ); }
  91.         ;
  92.  
  93. sect1end    :  SECTEND
  94.         ;
  95.  
  96. startconddecl   :  SCDECL
  97.             {
  98.             /* these productions are separate from the s1object
  99.              * rule because the semantics must be done before
  100.              * we parse the remainder of an s1object
  101.              */
  102.  
  103.             xcluflg = false;
  104.             }
  105.         
  106.         |  XSCDECL
  107.             { xcluflg = true; }
  108.         ;
  109.  
  110. namelist1    :  namelist1 WHITESPACE NAME
  111.             { scinstal( nmstr, xcluflg ); }
  112.  
  113.         |  NAME
  114.             { scinstal( nmstr, xcluflg ); }
  115.  
  116.         |  error
  117.                         { synerr( "bad start condition list" ); }
  118.         ;
  119.  
  120. sect2           :  sect2 initforrule flexrule '\n'
  121.         |
  122.         ;
  123.  
  124. initforrule     :
  125.             {
  126.             /* initialize for a parse of one rule */
  127.             trlcontxt = variable_trail_rule = varlength = false;
  128.             trailcnt = headcnt = rulelen = 0;
  129.             current_state_type = STATE_NORMAL;
  130.             previous_continued_action = continued_action;
  131.             new_rule();
  132.             }
  133.         ;
  134.  
  135. flexrule        :  scon '^' re eol 
  136.                         {
  137.             pat = link_machines( $3, $4 );
  138.             finish_rule( pat, variable_trail_rule,
  139.                      headcnt, trailcnt );
  140.  
  141.             for ( i = 1; i <= actvp; ++i )
  142.                 scbol[actvsc[i]] =
  143.                 mkbranch( scbol[actvsc[i]], pat );
  144.  
  145.             if ( ! bol_needed )
  146.                 {
  147.                 bol_needed = true;
  148.  
  149.                 if ( performance_report )
  150.                 fprintf( stderr,
  151.             "'^' operator results in sub-optimal performance\n" );
  152.                 }
  153.             }
  154.  
  155.         |  scon re eol 
  156.                         {
  157.             pat = link_machines( $2, $3 );
  158.             finish_rule( pat, variable_trail_rule,
  159.                      headcnt, trailcnt );
  160.  
  161.             for ( i = 1; i <= actvp; ++i )
  162.                 scset[actvsc[i]] = 
  163.                 mkbranch( scset[actvsc[i]], pat );
  164.             }
  165.  
  166.                 |  '^' re eol 
  167.             {
  168.             pat = link_machines( $2, $3 );
  169.             finish_rule( pat, variable_trail_rule,
  170.                      headcnt, trailcnt );
  171.  
  172.             /* add to all non-exclusive start conditions,
  173.              * including the default (0) start condition
  174.              */
  175.  
  176.             for ( i = 1; i <= lastsc; ++i )
  177.                 if ( ! scxclu[i] )
  178.                 scbol[i] = mkbranch( scbol[i], pat );
  179.  
  180.             if ( ! bol_needed )
  181.                 {
  182.                 bol_needed = true;
  183.  
  184.                 if ( performance_report )
  185.                 fprintf( stderr,
  186.             "'^' operator results in sub-optimal performance\n" );
  187.                 }
  188.             }
  189.  
  190.                 |  re eol 
  191.             {
  192.             pat = link_machines( $1, $2 );
  193.             finish_rule( pat, variable_trail_rule,
  194.                      headcnt, trailcnt );
  195.  
  196.             for ( i = 1; i <= lastsc; ++i )
  197.                 if ( ! scxclu[i] )
  198.                 scset[i] = mkbranch( scset[i], pat );
  199.             }
  200.  
  201.                 |  scon EOF_OP
  202.             { build_eof_action(); }
  203.  
  204.                 |  EOF_OP
  205.             {
  206.             /* this EOF applies only to the INITIAL start cond. */
  207.             actvsc[actvp = 1] = 1;
  208.             build_eof_action();
  209.             }
  210.  
  211.                 |  error
  212.             { synerr( "unrecognized rule" ); }
  213.         ;
  214.  
  215. scon            :  '<' namelist2 '>'
  216.         ;
  217.  
  218. namelist2       :  namelist2 ',' NAME
  219.                         {
  220.             if ( (scnum = sclookup( nmstr )) == 0 )
  221.                 lerrsf( "undeclared start condition %s", nmstr );
  222.  
  223.             else
  224.                 actvsc[++actvp] = scnum;
  225.             }
  226.  
  227.         |  NAME
  228.             {
  229.             if ( (scnum = sclookup( nmstr )) == 0 )
  230.                 lerrsf( "undeclared start condition %s", nmstr );
  231.             else
  232.                 actvsc[actvp = 1] = scnum;
  233.             }
  234.  
  235.         |  error
  236.             { synerr( "bad start condition list" ); }
  237.         ;
  238.  
  239. eol             :  '$'
  240.                         {
  241.             if ( trlcontxt )
  242.                 {
  243.                 synerr( "trailing context used twice" );
  244.                 $$ = mkstate( SYM_EPSILON );
  245.                 }
  246.             else
  247.                 {
  248.                 trlcontxt = true;
  249.  
  250.                 if ( ! varlength )
  251.                 headcnt = rulelen;
  252.  
  253.                 ++rulelen;
  254.                 trailcnt = 1;
  255.  
  256.                 eps = mkstate( SYM_EPSILON );
  257.                 $$ = link_machines( eps, mkstate( '\n' ) );
  258.                 }
  259.             }
  260.  
  261.         |
  262.                 {
  263.                 $$ = mkstate( SYM_EPSILON );
  264.  
  265.             if ( trlcontxt )
  266.                 {
  267.                 if ( varlength && headcnt == 0 )
  268.                 /* both head and trail are variable-length */
  269.                 variable_trail_rule = true;
  270.                 else
  271.                 trailcnt = rulelen;
  272.                 }
  273.                 }
  274.         ;
  275.  
  276. re              :  re '|' series
  277.                         {
  278.             varlength = true;
  279.  
  280.             $$ = mkor( $1, $3 );
  281.             }
  282.  
  283.         |  re2 series
  284.             {
  285.             if ( transchar[lastst[$2]] != SYM_EPSILON )
  286.                 /* provide final transition \now/ so it
  287.                  * will be marked as a trailing context
  288.                  * state
  289.                  */
  290.                 $2 = link_machines( $2, mkstate( SYM_EPSILON ) );
  291.  
  292.             mark_beginning_as_normal( $2 );
  293.             current_state_type = STATE_NORMAL;
  294.  
  295.             if ( previous_continued_action )
  296.                 {
  297.                 /* we need to treat this as variable trailing
  298.                  * context so that the backup does not happen
  299.                  * in the action but before the action switch
  300.                  * statement.  If the backup happens in the
  301.                  * action, then the rules "falling into" this
  302.                  * one's action will *also* do the backup,
  303.                  * erroneously.
  304.                  */
  305.                 if ( ! varlength || headcnt != 0 )
  306.                 {
  307.                 fprintf( stderr,
  308.     "flex: warning - trailing context rule at line %d made variable because\n",
  309.                      linenum );
  310.                 fprintf( stderr,
  311.                      "      of preceding '|' action\n" );
  312.                 }
  313.  
  314.                 /* mark as variable */
  315.                 varlength = true;
  316.                 headcnt = 0;
  317.                 }
  318.  
  319.             if ( varlength && headcnt == 0 )
  320.                 { /* variable trailing context rule */
  321.                 /* mark the first part of the rule as the accepting
  322.                  * "head" part of a trailing context rule
  323.                  */
  324.                 /* by the way, we didn't do this at the beginning
  325.                  * of this production because back then
  326.                  * current_state_type was set up for a trail
  327.                  * rule, and add_accept() can create a new
  328.                  * state ...
  329.                  */
  330.                 add_accept( $1, num_rules | YY_TRAILING_HEAD_MASK );
  331.                 }
  332.  
  333.             $$ = link_machines( $1, $2 );
  334.             }
  335.  
  336.         |  series
  337.             { $$ = $1; }
  338.         ;
  339.  
  340.  
  341. re2        :  re '/'
  342.             {
  343.             /* this rule is separate from the others for "re" so
  344.              * that the reduction will occur before the trailing
  345.              * series is parsed
  346.              */
  347.  
  348.             if ( trlcontxt )
  349.                 synerr( "trailing context used twice" );
  350.             else
  351.                 trlcontxt = true;
  352.  
  353.             if ( varlength )
  354.                 /* we hope the trailing context is fixed-length */
  355.                 varlength = false;
  356.             else
  357.                 headcnt = rulelen;
  358.  
  359.             rulelen = 0;
  360.  
  361.             current_state_type = STATE_TRAILING_CONTEXT;
  362.             $$ = $1;
  363.             }
  364.         ;
  365.  
  366. series          :  series singleton
  367.                         {
  368.             /* this is where concatenation of adjacent patterns
  369.              * gets done
  370.              */
  371.             $$ = link_machines( $1, $2 );
  372.             }
  373.  
  374.         |  singleton
  375.             { $$ = $1; }
  376.         ;
  377.  
  378. singleton       :  singleton '*'
  379.                         {
  380.             varlength = true;
  381.  
  382.             $$ = mkclos( $1 );
  383.             }
  384.             
  385.         |  singleton '+'
  386.             {
  387.             varlength = true;
  388.  
  389.             $$ = mkposcl( $1 );
  390.             }
  391.  
  392.         |  singleton '?'
  393.             {
  394.             varlength = true;
  395.  
  396.             $$ = mkopt( $1 );
  397.             }
  398.  
  399.         |  singleton '{' NUMBER ',' NUMBER '}'
  400.             {
  401.             varlength = true;
  402.  
  403.             if ( $3 > $5 || $3 < 0 )
  404.                 {
  405.                 synerr( "bad iteration values" );
  406.                 $$ = $1;
  407.                 }
  408.             else
  409.                 {
  410.                 if ( $3 == 0 )
  411.                 $$ = mkopt( mkrep( $1, $3, $5 ) );
  412.                 else
  413.                 $$ = mkrep( $1, $3, $5 );
  414.                 }
  415.             }
  416.                 
  417.         |  singleton '{' NUMBER ',' '}'
  418.             {
  419.             varlength = true;
  420.  
  421.             if ( $3 <= 0 )
  422.                 {
  423.                 synerr( "iteration value must be positive" );
  424.                 $$ = $1;
  425.                 }
  426.  
  427.             else
  428.                 $$ = mkrep( $1, $3, INFINITY );
  429.             }
  430.  
  431.         |  singleton '{' NUMBER '}'
  432.             {
  433.             /* the singleton could be something like "(foo)",
  434.              * in which case we have no idea what its length
  435.              * is, so we punt here.
  436.              */
  437.             varlength = true;
  438.  
  439.             if ( $3 <= 0 )
  440.                 {
  441.                 synerr( "iteration value must be positive" );
  442.                 $$ = $1;
  443.                 }
  444.  
  445.             else
  446.                 $$ = link_machines( $1, copysingl( $1, $3 - 1 ) );
  447.             }
  448.  
  449.         |  '.'
  450.             {
  451.             if ( ! madeany )
  452.                 {
  453.                 /* create the '.' character class */
  454.                 anyccl = cclinit();
  455.                 ccladd( anyccl, '\n' );
  456.                 cclnegate( anyccl );
  457.  
  458.                 if ( useecs )
  459.                 mkeccl( ccltbl + cclmap[anyccl],
  460.                     ccllen[anyccl], nextecm,
  461.                     ecgroup, CSIZE );
  462.                 
  463.                 madeany = true;
  464.                 }
  465.  
  466.             ++rulelen;
  467.  
  468.             $$ = mkstate( -anyccl );
  469.             }
  470.  
  471.         |  fullccl
  472.             {
  473.             if ( ! cclsorted )
  474.                 /* sort characters for fast searching.  We use a
  475.                  * shell sort since this list could be large.
  476.                  */
  477.                 cshell( ccltbl + cclmap[$1], ccllen[$1] );
  478.  
  479.             if ( useecs )
  480.                 mkeccl( ccltbl + cclmap[$1], ccllen[$1],
  481.                     nextecm, ecgroup, CSIZE );
  482.                      
  483.             ++rulelen;
  484.  
  485.             $$ = mkstate( -$1 );
  486.             }
  487.  
  488.         |  PREVCCL
  489.             {
  490.             ++rulelen;
  491.  
  492.             $$ = mkstate( -$1 );
  493.             }
  494.  
  495.         |  '"' string '"'
  496.             { $$ = $2; }
  497.  
  498.         |  '(' re ')'
  499.             { $$ = $2; }
  500.  
  501.         |  CHAR
  502.             {
  503.             ++rulelen;
  504.  
  505.             if ( $1 == '\0' )
  506.                 synerr( "null in rule" );
  507.  
  508.             if ( caseins && $1 >= 'A' && $1 <= 'Z' )
  509.                 $1 = clower( $1 );
  510.  
  511.             $$ = mkstate( $1 );
  512.             }
  513.         ;
  514.  
  515. fullccl        :  '[' ccl ']'
  516.             { $$ = $2; }
  517.  
  518.         |  '[' '^' ccl ']'
  519.             {
  520.             /* *Sigh* - to be compatible Unix lex, negated ccls
  521.              * match newlines
  522.              */
  523. #ifdef NOTDEF
  524.             ccladd( $3, '\n' ); /* negated ccls don't match '\n' */
  525.             cclsorted = false; /* because we added the newline */
  526. #endif
  527.             cclnegate( $3 );
  528.             $$ = $3;
  529.             }
  530.         ;
  531.  
  532. ccl             :  ccl CHAR '-' CHAR
  533.                         {
  534.             if ( $2 > $4 )
  535.                 synerr( "negative range in character class" );
  536.  
  537.             else
  538.                 {
  539.                 if ( caseins )
  540.                 {
  541.                 if ( $2 >= 'A' && $2 <= 'Z' )
  542.                     $2 = clower( $2 );
  543.                 if ( $4 >= 'A' && $4 <= 'Z' )
  544.                     $4 = clower( $4 );
  545.                 }
  546.  
  547.                 for ( i = $2; i <= $4; ++i )
  548.                     ccladd( $1, i );
  549.  
  550.                 /* keep track if this ccl is staying in alphabetical
  551.                  * order
  552.                  */
  553.                 cclsorted = cclsorted && ($2 > lastchar);
  554.                 lastchar = $4;
  555.                 }
  556.             
  557.             $$ = $1;
  558.             }
  559.  
  560.         |  ccl CHAR
  561.                 {
  562.             if ( caseins )
  563.                 if ( $2 >= 'A' && $2 <= 'Z' )
  564.                 $2 = clower( $2 );
  565.  
  566.             ccladd( $1, $2 );
  567.             cclsorted = cclsorted && ($2 > lastchar);
  568.             lastchar = $2;
  569.             $$ = $1;
  570.             }
  571.  
  572.         |
  573.             {
  574.             cclsorted = true;
  575.             lastchar = 0;
  576.             $$ = cclinit();
  577.             }
  578.         ;
  579.  
  580. string        :  string CHAR
  581.                         {
  582.             if ( caseins )
  583.                 if ( $2 >= 'A' && $2 <= 'Z' )
  584.                 $2 = clower( $2 );
  585.  
  586.             ++rulelen;
  587.  
  588.             $$ = link_machines( $1, mkstate( $2 ) );
  589.             }
  590.  
  591.         |
  592.             { $$ = mkstate( SYM_EPSILON ); }
  593.         ;
  594.  
  595. %%
  596.  
  597.  
  598. /* build_eof_action - build the "<<EOF>>" action for the active start
  599.  *                    conditions
  600.  */
  601.  
  602. build_eof_action()
  603.  
  604.     {
  605.     register int i;
  606.  
  607.     for ( i = 1; i <= actvp; ++i )
  608.     {
  609.     if ( sceof[actvsc[i]] )
  610.         lerrsf( "multiple <<EOF>> rules for start condition %s",
  611.             scname[actvsc[i]] );
  612.  
  613.     else
  614.         {
  615.         sceof[actvsc[i]] = true;
  616.         fprintf( temp_action_file, "case YY_STATE_EOF(%s):\n",
  617.              scname[actvsc[i]] );
  618.         }
  619.     }
  620.  
  621.     line_directive_out( temp_action_file );
  622.     }
  623.  
  624.  
  625. /* synerr - report a syntax error
  626.  *
  627.  * synopsis
  628.  *    char str[];
  629.  *    synerr( str );
  630.  */
  631.  
  632. synerr( str )
  633. char str[];
  634.  
  635.     {
  636.     syntaxerror = true;
  637.     fprintf( stderr, "Syntax error at line %d: %s\n", linenum, str );
  638.     }
  639.  
  640.  
  641. /* yyerror - eat up an error message from the parser
  642.  *
  643.  * synopsis
  644.  *    char msg[];
  645.  *    yyerror( msg );
  646.  */
  647.  
  648. yyerror( msg )
  649. char msg[];
  650.  
  651.     {
  652.     }
  653.